Error correction is implemented most commonly in digital communications through an encoding apparatus at the data source for developing redundant information in a mathematically prescribed manner for transmission over a data channel (which may include information storage media) to a data sink at which an error correction decoder detects, locates, and corrects combinations of errors in the information stream. A well known enhancement for error correction apparatus is achieved by independently encoding a number of information units (hereafter, codewords) and shuffling, or resequencing constituent information subunits of the codewords (hereafter, characters) among the several independently encoded codewords for transmitting the data stream in a particular sequence over the data channel. An inverse operation at the data sink (or receiver) restores the original sequential order of constituent characters and thereby the respective codewords are reconstituted and presented to the decoder for detection of error. This process is known in the art as "interleaving".
It is apparent that interleaving presents a particular enhancement for error correction schemes where bursts of noise or fading of signal in the channel produces a sequence of erasures at the data sink. In such instance, error correction apparatus capable of withstanding some number of errors in a local span of the data stream may be overwhelmed, whereas the resequencing of the data stream more evenly distributes the burst elements over independently encoded regions of the data stream.
It is appropriate to point out that interleaving as discussed herein is distinct from the practice of altering the physical sequencing of information units stored on rotating memory. The object of that practice is the reduction of latency times and optimization for sequential retreival of information units. The physical resequencing to obtain monotonic sequential data retrieval is contrasted with the present re-sequencing which is practiced to more uniformly distribute the effects of noise bursts, fading and like signal degradation.
One representative of prior art is the classic block interleaver. This is best understood in a model block interleaver which may be considered as an array of memory elements arranged as N rows of I columns. Assume that encoded information (codewords) comprises N symbols and further that I codewords are to be interleaved (the depth of the interleaver). Symbols enter the interleaver sequentially by columns. Thus codewords reside in resepctive columns of the array. Output from the block interleaver to the modem occurs serially by rows, thereby producing the desired re-sequencing for exposure to the hazards of transmission. At the receiver, the de-interleaver accepts the data stream for storage by rows. Output from the de-interleaver to the decoder occurs by columns, thereby reconstituting the respective codewords from their interleaved symbols.
A few salient properties of the block interleaver deserve comment. The objection of uniformly distributing burst errors is certainly achieved if the burst length (measured in code symbol intervals) is less than the interleaving depth. In such instance the de-interleaver output will contain no more than a single error in any codeword. If the burst length is in excess of any multiple M of the interleaving depth I, at least M errors will be present in the block of interleaved codewords at the output of the interleaver.
Due to the simple periodicity of the block interleaver, a periodic sequence of single bits errors, spaced in time by the interleaving depth, will result in a single burst of errors at the de-interleaver output. One appreciates that the periodicity of the interleaver necessitates synchronization between interleavers at transmitter and receiver.
Accordingly, it is an object of the present invention to implement a novel and improved interleaver which is greatly reduced in complexity, thereby reducing the number of components required.
It is another object to achieve an interleaver which has greatly reduced requirement for the time period required for synchronization with another like interleaver in communication therewith.
It is yet another object to utilize an interleaving technique which minimizes the effect upon an error correction decoder of the phase or time-of-occurence of a noise burst.
It is one other object of the invention to implement a novel synchronization technique for defining the relative phase of interleaver and de-interleaver.